package leetcode.interviewClassics;

/**
 * @author Cheng Jun
 * Description: 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * @version 1.0
 * @date 2021/11/9 22:57
 */
public class maxSubArray {

    public static void main(String[] args) {
        maxSubArray1(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
    }

    // 遍历每个数字，以每个数字为起点都有一个最大值，如果累加过程中出现小于 0 的情况，从下一个数重新计算累加值
    // 时间复杂度 O(n) 空间复杂度 O(1)
    static int maxSubArray(int[] nums) {
        int maxSub = nums[0];
        int indexMaxSub = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 累计的结果 小于等于 0 就可以重新开始
            if (indexMaxSub <= 0) {
                indexMaxSub = nums[i];
            } else {
                indexMaxSub += nums[i];
            }
            maxSub = Math.max(maxSub, indexMaxSub);
        }
        return maxSub;
    }

    // 优化代码 maxSubArray
    // 空间复杂度，时间复杂度不变，仅仅优化编码
    static int maxSubArray1(int[] nums) {
        int maxSub = nums[0];
        int indexMaxSub = 0;
        for (int num : nums) {
            indexMaxSub = Math.max(num, indexMaxSub + num);
            maxSub = Math.max(maxSub, indexMaxSub);
        }
        return maxSub;
    }
}
